package binary;

import java.util.Arrays;
import java.util.Objects;

/**
 * leet-code(34) 在排序数组中查找元素的第一个和最后一个位置
 * https://mp.weixin.qq.com/s/1ExIav9uK4bvVnnf4t0H2Q
 *
 * @auther yang
 * @date 2022/3/18 9:49
 */
public class SearchRange {

    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 8, 10};
        int[] result = searchRange(nums, 6);
        System.out.println(Arrays.toString(result));
    }

    public static int[] searchRange(int[] nums, int target) {
        if (Objects.isNull(nums) || nums.length < 1) return new int[]{-1, -1};

        int left = leftBound(nums, target);
        int right = rightBound(nums, target);

        if (left > right) return new int[]{-1, -1};
        return new int[]{left, right};
    }

    private static int leftBound(int[] a, int target) {

        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            if (target <= a[mid]) hi = mid - 1;
            else lo = mid + 1;
        }
        return lo;
    }

    private static int rightBound(int[] a, int target) {
        int lo = 0, hi = a.length - 1;
        while (lo <= hi) {
            int mid = lo + ((hi - lo) >> 1);
            if (target >= a[mid]) lo = mid + 1;
            else hi = mid - 1;
        }
        return hi;
    }
}
